package org.example.BinaryTree;

public class Insertion_operations_in_binary_search_trees {
    public static void main(String[] args) {
        //二叉搜索树中的插入操作

        //给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
        //注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(7);
        TreeNode node3 = new TreeNode(1);
        TreeNode node4 = new TreeNode(3);
        TreeNode root = new TreeNode(4);
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        TreeNode treeNode = insertIntoBST(root, 0);
        search(treeNode);
    }
    public static TreeNode insertIntoBST(TreeNode root, int val) {
        if (root==null) return new TreeNode(val);
        insertNode(root,val);
        return root;
    }
    //本质上是前序遍历，处理中结点
    public static void insertNode(TreeNode node, int val){
        if (val<node.val&&node.left==null){
            node.left = new TreeNode(val);
        }else if (val>node.val&&node.right==null){
            node.right = new TreeNode(val);
        }else if (val<node.val){
            insertNode(node.left,val);
        }else {
            insertNode(node.right,val);
        }
    }

    public static void search(TreeNode node){
        if (node==null) return;
        System.out.print(node.val+" ");
        search(node.left);
        search(node.right);
    }
}
